Search for: All records

We prove that the most natural low-degree test for polynomials over finite fields is “robust” in the high-error regime for linear-sized fields. Specifically we consider the “local” agreement of a function $$f:\mathbb{F}_{q}^{m}\rightarrow \mathbb{F}_{q}$$ from the space of degree-d polynomials, i.e., the expected agreement of the function from univariate degree-d polynomials over a randomly chosen line in $$\mathbb{F}_{q}^{m}$$, and prove that if this local agreement is $$\varepsilon\geq\Omega((d/q)^{\tau}))$$ for some fixed $$\tau > 0$$, then there is a global degree-d polynomial $$Q:\mathbb{F}_{q}^{m}\rightarrow \mathbb{F}_{q}$$ with agreement nearly $$\varepsilon$$ with $$f$$. This settles a long-standing open question in the area of low-degree testing, yielding an $O(d)$ -query robust test in the “high-error” regime (i.e., when $$\varepsilon < 1/2)$$. The previous results in this space either required $$\varepsilon > 1/2$$ (Polishchuk & Spielman, STOC 1994), or $$q=\Omega(d^{4})$$ (Arora & Sudan, Combinatorica 2003), orneeded to measure local distance on 2-dimensional “planes” rather than one-dimensional lines leading to $$\Omega(d^{2})$$ -query complexity (Raz & Safra, STOC 1997). Our analysis follows the spirit of most previous analyses in first analyzing the low-variable case $(m=O(1))$ and then “boot-strapping” to general multivariate settings. Our main technical novelty is a new analysis in the bivariate setting that exploits a previously known connection between multivariate factorization and finding (or testing) low-degree polynomials, in a non “black-box” manner. This connection was used roughly in a black-box manner in the work of Arora & Sudan — and we show that opening up this black box and making some delicate choices in the analysis leads to our essentially optimal analysis. A second contribution is a bootstrapping analysis which manages to lift analyses for $m=2$ directly to analyses for general $$m$$, where previous works needed to work with $m=3$ or $m=4$ — arguably this bootstrapping is significantly simpler than those in prior works. 

We prove that the most natural low-degree test for polynomials over finite fields is “robust” in the high-error regime for linear-sized fields. Specifically we consider the “local” agreement of a function $$f:\mathbb{F}_{q}^{m}\rightarrow \mathbb{F}_{q}$$ from the space of degree-d polynomials, i.e., the expected agreement of the function from univariate degree-d polynomials over a randomly chosen line in $$\mathbb{F}_{q}^{m}$$, and prove that if this local agreement is $$\varepsilon\geq\Omega((d/q)^{\tau}))$$ for some fixed $$\tau > 0$$, then there is a global degree-d polynomial $$Q:\mathbb{F}_{q}^{m}\rightarrow \mathbb{F}_{q}$$ with agreement nearly $$\varepsilon$$ with $$f$$. This settles a long-standing open question in the area of low-degree testing, yielding an $O(d)$ -query robust test in the “high-error” regime (i.e., when $$\varepsilon < 1/2)$$. The previous results in this space either required $$\varepsilon > 1/2$$ (Polishchuk & Spielman, STOC 1994), or $$q=\Omega(d^{4})$$ (Arora & Sudan, Combinatorica 2003), orneeded to measure local distance on 2-dimensional “planes” rather than one-dimensional lines leading to $$\Omega(d^{2})$$ -query complexity (Raz & Safra, STOC 1997). Our analysis follows the spirit of most previous analyses in first analyzing the low-variable case $(m=O(1))$ and then “boot-strapping” to general multivariate settings. Our main technical novelty is a new analysis in the bivariate setting that exploits a previously known connection between multivariate factorization and finding (or testing) low-degree polynomials, in a non “black-box” manner. This connection was used roughly in a black-box manner in the work of Arora & Sudan — and we show that opening up this black box and making some delicate choices in the analysis leads to our essentially optimal analysis. A second contribution is a bootstrapping analysis which manages to lift analyses for $m=2$ directly to analyses for general $$m$$, where previous works needed to work with $m=3$ or $m=4$ — arguably this bootstrapping is significantly simpler than those in prior works. 

In this work, we present an abstract framework for some algebraic error-correcting codes with the aim of capturing codes that are list-decodable to capacity, along with their decoding algorithms. In the polynomial ideal framework, a code is specified by some ideals in a polynomial ring, messages are polynomials and the encoding of a message polynomial is the collection of residues of that polynomial modulo the ideals. We present an alternate way of viewing this class of codes in terms of linear operators, and show that this alternate view makes their algorithmic list-decodability amenable to analysis. Our framework leads to a new class of codes that we call affine Folded Reed-Solomon codes (which are themselves a special case of the broader class we explore). These codes are common generalizations of the well-studied Folded Reed-Solomon codes and Univariate Multiplicity codes as well as the less-studied Additive Folded Reed-Solomon codes, and lead to a large family of codes that were not previously known/studied. More significantly our framework also captures the algorithmic list-decodability of the constituent codes. Specifically, we present a unified view of the decoding algorithm for ideal-theoretic codes and show that the decodability reduces to the analysis of the distance of some related codes. We show that a good bound on this distance leads to a capacity-achieving performance of the underlying code, providing a unifying explanation of known capacity-achieving results. In the specific case of affine Folded Reed-Solomon codes, our framework shows that they are efficiently list-decodable up to capacity (for appropriate setting of the parameters), thereby unifying the previous results for Folded Reed-Solomon, Multiplicity and Additive Folded Reed-Solomon codes. 

The multiplicity Schwartz-Zippel lemma bounds the total multiplicity of zeroes of a multivariate polynomial on a product set. This lemma motivates the multiplicity codes of Kopparty, Saraf and Yekhanin [J. ACM, 2014], who showed how to use this lemma to construct high-rate locally-decodable codes. However, the algorithmic results about these codes crucially rely on the fact that the polynomials are evaluated on a vector space and not an arbitrary product set. In this work, we show how to decode multivariate multiplicity codes of large multiplicities in polynomial time over finite product sets (over fields of large characteristic and zero characteristic). Previously such decoding algorithms were not known even for a positive fraction of errors. In contrast, our work goes all the way to the distance of the code and in particular exceeds both the unique-decoding bound and the Johnson radius. For errors exceeding the Johnson radius, even combinatorial list-decodablity of these codes was not known. Our algorithm is an application of the classical polynomial method directly to the multivariate setting. In particular, we do not rely on a reduction from the multivariate to the univariate case as is typical of many of the existing results on decoding codes based on multivariate polynomials. However, a vanilla application of the polynomial method in the multivariate setting does not yield a polynomial upper bound on the list size. We obtain a polynomial bound on the list size by taking an alternative view of multivariate multiplicity codes. In this view, we glue all the partial derivatives of the same order together using a fresh set z of variables. We then apply the polynomial method by viewing this as a problem over the field F(z) of rational functions in z . 

As industries transition into the Industry 4.0 paradigm, the relevance and interest in concepts like Digital Twin (DT) are at an all-time high. DTs offer direct avenues for industries to make more accurate predictions, rational decisions, and informed plans, ultimately reducing costs, increasing performance and productivity. Adequate operation of DTs in the context of smart manufacturing relies on an evolving data-set relating to the real-life object or process, and a means of dynamically updating the computational model to better conform to the data. This reliance on data is made more explicit when physics-based computational models are not available or difficult to obtain in practice, as it's the case in most modern manufacturing scenarios. For data-based model surrogates to adequately represent the underlying physics, the number of training data points must keep pace with the number of degrees of freedom in the model, which can be on the order of thousands. However, in niche industrial scenarios like the one in manufacturing applications, the availability of data is limited (on the order of a few hundred data points, at best), mainly because a manual measuring process typically must take place for a few of the relevant quantities, e.g., level of wear of a tool. In other words, notwithstanding the popular notion of big-data, there is still a stark shortage of ground-truth data when examining, for instance, a complex system's path to failure. In this work we present a framework to alleviate this problem via modern machine learning tools, where we show a robust, efficient and reliable pathway to augment the available data to train the data-based computational models. Small sample size data is a key limitation in performance in machine learning, in particular with very high dimensional data. Current efforts for synthetic data generation typically involve either Generative Adversarial Networks (GANs) or Variational AutoEncoders (VAEs). These, however, are are tightly related to image processing and synthesis, and are generally not suited for sensor data generation, which is the type of data that manufacturing applications produce. Additionally, GAN models are susceptible to mode collapse, training instability, and high computational costs when used for high dimensional data creation. Alternatively, the encoding of VAEs greatly reduces dimensional complexity of data and can effectively regularize the latent space, but often produces poor representational synthetic samples. Our proposed method thus incorporates the learned latent space from an AutoEncoder (AE) architecture into the training of the generation network in a GAN. The advantages of such scheme are twofold: \textbf{(\textit{i})} the latent space representation created by the AE reduces the complexity of the distribution the generator must learn, allowing for quicker discriminator convergence, and \textbf{(\textit{ii})} the structure in the sensor data is better captured in the transition from the original space to the latent space. Through time statistics (up to the fifth moment), ARIMA coefficients and Fourier series coefficients, we compare the synthetic data from our proposed AE+GAN model with the original sensor data. We also show that the performance of our proposed method is at least comparable with that of the Riemannian Hamiltonian VAE, which is a recently published data augmentation framework specifically designed to handle very small high dimensional data sets. 

This work presents an integrated architecture for a prognostic digital twin for smart manufacturing subsystems. The specific case of cutting tool wear (flank wear) in a CNC machine is considered, using benchmark data sets provided by the Prognostics and Health Management (PHM) Society. This paper emphasizes the role of robust uncertainty quantification, especially in the presence of data-driven black- and gray-box dynamic models. A surrogate dynamic model is constructed to track the evolution of flank wear using a reduced set of features extracted from multi-modal sensor time series data. The digital twin's uncertainty quantification engine integrates with this dynamic model along with a machine emulator that is tasked with generating future operating scenarios for the machine. The surrogate dynamic model and emulator are combined in a closed-loop architecture with an adaptive Monte Carlo uncertainty forecasting framework that allows prediction of quantities of interest critical to prognostics within user-prescribed bounds. Numerical results using the PHM dataset are shown illustrating how the adaptive uncertainty forecasting tools deliver a trustworthy forecast by maintaining predictive error within the prescribed tolerance. 

This article presents a new evidential reasoning approach for estimating the state of an evolving wildfire in real time. Given assumed terrain information and localized wind velocity distribution parameters, a probabilistic representation (i.e., the belief state) of a wildfire is forecast across the spatiotemporal domain through a compilation of fire spread simulations. The forecast is updated through information fusion based on observations provided by: 1) embedded temperature sensors and 2) mobile vision agents that are advantageously directed toward locations of information extraction based on the current state estimate. This combination of uncertain sources is performed under the evidence-based Dempster’s rule of combination and is then used to enact sensor reconfiguration based on the updated estimate. This research finds that the evidential belief combination vastly outperforms the standard forecasting approach (where no sensor data are incorporated) in the presence of imprecise environmental parameters. 

This paper considers path planning with resource constraints and dynamic obstacles for an unmanned aerial vehicle (UAV), modeled as a Dubins agent. Incorporating these complex constraints at the guidance stage expands the scope of operations of UAVs in challenging environments containing path-dependent integral constraints and time-varying obstacles. Path-dependent integral constraints, also known as resource constraints, can occur when the UAV is subject to a hazardous environment that exposes it to cumulative damage over its traversed path. The noise penalty function was selected as the resource constraint for this study, which was modeled as a path integral that exerts a path-dependent load on the UAV, stipulated to not exceed an upper bound. Weather phenomena such as storms, turbulence and ice are modeled as dynamic obstacles. In this paper, ice data from the Aviation Weather Service is employed to create training data sets for learning the dynamics of ice phenomena. Dynamic mode decomposition (DMD) is used to learn and forecast the evolution of ice conditions at flight level. This approach is presented as a computationally scalable means of propagating obstacle dynamics. The reduced order DMD representation of time-varying ice obstacles is integrated with a recently developed backtracking hybridA∗ graph search algorithm. The backtracking mechanism allows us to determine a feasible path in a computationally scalable manner in the presence of resource constraints. Illustrative numerical results are presented to demonstrate the effectiveness of the proposed path-planning method.